`
https://leetcode.cn/problems/all-nodes-distance-k-in-binary-tree/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function (root, target, k) {
  // 可以把树转换成图，再用BFS查一次即可

  // 记录节点的父节点 node.val -> node
  const parent = new Map()
  function traverse(node, parentNode) {
    if (node === null) return
    // 题目已说 Node.val 是唯一的，所以可以拿来当键
    parent.set(node.val, parentNode)
    traverse(node.left, node)
    traverse(node.right, node)
  }
  traverse(root, null)

  const q = [target]
  const visited = new Set()
  visited.add(target.val)
  const res = []
  let dist = 0

  // dfs遍历
  while (q.length) {
    const sz = q.length
    for (let i = 0; i < sz; i++) {
      const cur = q.shift()
      // 找到距离为 k 的节点
      if (dist === k) {
        res.push(cur.val)
      }
      const parentNode = parent.get(cur.val)
      if (parentNode && !visited.has(parentNode.val)) {
        visited.add(parentNode.val)
        q.push(parentNode)
      }
      if (cur.left && !visited.has(cur.left.val)) {
        visited.add(cur.left.val)
        q.push(cur.left)
      }
      if (cur.right && !visited.has(cur.right.val)) {
        visited.add(cur.right.val)
        q.push(cur.right)
      }
    }
    // 向外扩展一圈
    dist++
  }

  return res
};